/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

// 合并两个已经有序的链表
// 我们这里可以设多个指针函数解决
// 给链表1和链表2各设置一个指针进行遍历及比较大小
// 再设立一个指针,将对比结果进行连接
// 由于是两个向比较,所以肯定会出现一条提前比完的情况
// 所以在最后将未比完的链表连入新链表的后面即可

// 除此之外,还有一个问题就是面对两个链表,如果要一开始在两个链表里面决定头结点,代码量会多很多
// 所以这里新创建了一个哨兵位(头节点),两个链表的节点比较之后就可以接入在哨兵位的后面了

typedef struct ListNode ListNode ;

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{

    // 当任意链表为空的时候,可以直接返回另外一个非空链表

    if (list1 == NULL)
    {

        return list2 ;

    }

    if (list2 == NULL)
    {

        return list1 ;

    }

    ListNode* pos = (ListNode*) malloc (sizeof (ListNode)) ; // 这里创建了哨兵位,减少了代码量

    ListNode* ptail = pos ;

    ListNode* src = list1 ;

    ListNode* des = list2 ;

    while (src && des) // 这里当任意链表遍历完了之后,就结束循环,另外一个链表的剩余节点连接在末尾
    {

        if (src -> val < des -> val)
        {

            ptail -> next = src ;

            src = src -> next ;

            ptail = ptail-> next ;

        }

        else
        {

            ptail -> next = des ;

            des = des -> next ;

            ptail = ptail -> next ;

        }

    }

    if (src)
    {

        ptail -> next = src ;

    }

    if (des)
    {

        ptail -> next = des ;
        
    }

    return pos -> next ;
    
}